# Tokénisation <i>WordPiece</i>

<CourseFloatingBanner chapter={6}
  classNames="absolute z-10 right-0 top-0"
  notebooks={[
    {label: "English", value: "https://colab.research.google.com/github/huggingface/notebooks/blob/master/course/en/chapter6/section6.ipynb"},
    {label: "Français", value: "https://colab.research.google.com/github/huggingface/notebooks/blob/master/course/fr/chapter6/section6.ipynb"},
    {label: "English", value: "https://studiolab.sagemaker.aws/import/github/huggingface/notebooks/blob/master/course/en/chapter6/section6.ipynb"},
    {label: "Français", value: "https://studiolab.sagemaker.aws/import/github/huggingface/notebooks/blob/master/course/fr/chapter6/section6.ipynb"},
]} />

*WordPiece* est l'algorithme de tokénisation développé par Google pour prétraîner BERT. Il a depuis été réutilisé dans un grand nombre de modèles de *transformers* basés sur BERT tels que DistilBERT, MobileBERT, Funnel Transformers et MPNET. Il est très similaire au BPE en termes d'entraînement mais la tokenisation réelle est effectuée différemment.

<Youtube id="qpv6ms_t_1A"/>

> [!TIP]
> 💡 Cette section couvre le <i>WordPiece</i> en profondeur, allant jusqu'à montrer une implémentation complète. Vous pouvez passer directement à la fin si vous souhaitez simplement avoir un aperçu général de l'algorithme de tokénisation.

## Algorithme d'entraînement

> [!WARNING]
> ⚠️ Google n'a jamais mis en ligne son implémentation de l'algorithme d'entraînement du <i>WordPiece</i>. Ce qui suit est donc notre meilleure estimation basée sur la littérature publiée. Il se peut qu'elle ne soit pas exacte à 100 %.

Comme le BPE, *WordPiece* part d'un petit vocabulaire comprenant les *tokens* spéciaux utilisés par le modèle et l'alphabet initial. Puisqu'il identifie les sous-mots en ajoutant un préfixe (comme `##` pour BERT), chaque mot est initialement découpé en ajoutant ce préfixe à tous les caractères du mot. Ainsi par exemple, `"word"` est divisé comme ceci :

```
w ##o ##r ##d
```

Ainsi, l'alphabet initial contient tous les caractères présents au début d'un mot et les caractères présents à l'intérieur d'un mot précédé du préfixe de *WordPiece*.

Ensuite, toujours comme le BPE, *WordPiece* apprend des règles de fusion. La principale différence réside dans la manière dont la paire à fusionner est sélectionnée. Au lieu de sélectionner la paire la plus fréquente, *WordPiece* calcule un score pour chaque paire en utilisant la formule suivante :

$$\mathrm{score} = (\mathrm{freq\_of\_pair}) / (\mathrm{freq\_of\_first\_element} \times \mathrm{freq\_of\_second\_element})$$

En divisant la fréquence de la paire par le produit des fréquences de chacune de ses parties, l'algorithme donne la priorité à la fusion des paires dont les parties individuelles sont moins fréquentes dans le vocabulaire. Par exemple, il ne fusionnera pas nécessairement `("un", "##able")` même si cette paire apparaît très fréquemment dans le vocabulaire car les deux paires `"un"`" et `"##able"` apparaîtront probablement chacune dans un batch d'autres mots et auront une fréquence élevée. En revanche, une paire comme `("hu", "##gging")` sera probablement fusionnée plus rapidement (en supposant que le mot `"hugging"` apparaisse souvent dans le vocabulaire) puisque `"hu"` et `"##gging"` sont probablement moins fréquents individuellement.

Examinons le même vocabulaire que celui utilisé dans l'exemple d'entraînement du BPE :

```
("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)
```

Les divisions ici seront :

```
("h" "##u" "##g", 10), ("p" "##u" "##g", 5), ("p" "##u" "##n", 12), ("b" "##u" "##n", 4), ("h" "##u" "##g" "##s", 5)
```

Si on oublie les *tokens* spéciaux pour l'instant, le vocabulaire initial sera donc `["b", "h", "p", "##g", "##n", "##s", "##u"]`. La paire la plus fréquente est `("##u", "##g")` (présente 20 fois), mais la fréquence individuelle de `"##u"` est très élevée, donc son score n'est pas le plus élevé (il est de 1 / 36). Toutes les paires avec un `"##u"` ont en fait le même score (1 / 36). Ainsi le meilleur score va à la paire `("##g", "##s")` qui est la seule sans un `"##u"` avec un score 1 / 20. Et la première fusion apprise est `("##g", "##s") -> ("##gs")`.

Notez que lorsque nous fusionnons, nous enlevons le `##` entre les deux *tokens*, donc nous ajoutons `"##gs"` au vocabulaire et appliquons la fusion dans les mots du corpus :

```
Vocabulary: ["b", "h", "p", "##g", "##n", "##s", "##u", "##gs"]
Corpus: ("h" "##u" "##g", 10), ("p" "##u" "##g", 5), ("p" "##u" "##n", 12), ("b" "##u" "##n", 4), ("h" "##u" "##gs", 5)
```

À ce stade, `" ##u "` est dans toutes les paires possibles, donc elles finissent toutes par avoir le même score. Disons que dans ce cas, la première paire est fusionnée, donc `("h", "##u") -> "hu"`. Cela nous amène à :

```
Vocabulary: ["b", "h", "p", "##g", "##n", "##s", "##u", "##gs", "hu"]
Corpus: ("hu" "##g", 10), ("p" "##u" "##g", 5), ("p" "##u" "##n", 12), ("b" "##u" "##n", 4), ("hu" "##gs", 5)
```

Ensuite, le meilleur score suivant est partagé par `("hu", "##g")` et `("hu", "##gs")` (avec 1/15, comparé à 1/21 pour toutes les autres paires). Ainsi la première paire avec le plus grand score est fusionnée :

```
Vocabulary: ["b", "h", "p", "##g", "##n", "##s", "##u", "##gs", "hu", "hug"]
Corpus: ("hug", 10), ("p" "##u" "##g", 5), ("p" "##u" "##n", 12), ("b" "##u" "##n", 4), ("hu" "##gs", 5)
```

et nous continuons ainsi jusqu'à ce que nous atteignions la taille de vocabulaire souhaitée.

> [!TIP]
> ✏️ **A votre tour !** Quelle sera la prochaine règle de fusion ?

## Algorithme de tokenisation

La tokénisation diffère dans *WordPiece* et BPE en ce que *WordPiece* ne sauvegarde que le vocabulaire final et non pas les règles de fusion apprises. En partant du mot à tokeniser, *WordPiece* trouve le sous-mot le plus long qui se trouve dans le vocabulaire, puis se sépare sur celui-ci. Par exemple, si nous utilisons le vocabulaire appris dans l'exemple ci-dessus, pour le mot `"hugs"` le plus long sous-mot en partant du début qui est dans le vocabulaire est `"hug"`. Donc nous le divisons et obtenons `["hug", "##s"]`. On continue avec `"##s"`, qui est dans le vocabulaire, donc la tokenisation de `"hugs"` est `["hug", "##s"]`.

Avec BPE, nous aurions appliqué les fusions apprises dans l'ordre et la tokénisation aurait été `["hu", "##gs"]`, l'encodage est donc différent.

Comme autre exemple, voyons comment le mot `"bugs"` serait tokenisé. `"b"` est le plus long sous-mot commençant au début du mot qui est dans le vocabulaire donc on le divise et on obtient `["b", "##ugs"]`. Ensuite, `"##u"` est le plus long sous-mot commençant au début de `"##ugs"` qui est dans le vocabulaire, donc on le sépare et on obtient `["b", "##u, "##gs"]`. Enfin, `"##gs"` est dans le vocabulaire, donc cette dernière liste est la tokenization de `"bugs"`.

Lorsque la tokenisation arrive à un stade où il n'est pas possible de trouver un sous-mot dans le vocabulaire, le mot entier est tokenisé comme inconnu. Par exemple, `"mug"` serait tokenisé comme `["[UNK]"]`, tout comme `"bum"` (même si on peut commencer par " b " et " ##u ", " ##m " ne fait pas partie du vocabulaire, et le *tokenizer* résultant sera simplement `["[UNK]"]` " et non `["b", "##u", "[UNK]"]` "). C'est une autre différence avec le BPE qui classerait seulement les caractères individuels qui ne sont pas dans le vocabulaire comme inconnus.

> [!TIP]
> ✏️ **A votre tour !** Comment le mot `"pugs"` sera-t-il tokenisé ?

## Implémentation de <i>WordPiece</i>

Voyons maintenant une implémentation de l'algorithme *WordPiece*. Comme pour le BPE, il s'agit d'un exemple pédagogique et vous ne pourrez pas l'utiliser sur un grand corpus.

Nous utiliserons le même corpus que dans l'exemple BPE :

```python
corpus = [
    "This is the Hugging Face Course.",
    # C'est le cours d'Hugging Face.
    "This chapter is about tokenization.",
    # This chapter is about tokenization
    "This section shows several tokenizer algorithms.",
    # Cette section présente plusieurs algorithmes de tokenizer.
    "Hopefully, you will be able to understand how they are trained and generate tokens.",
    # Avec un peu de chance, vous serez en mesure de comprendre comment ils sont entraînés et génèrent des tokens.
]
```

Tout d'abord, nous devons prétokéniser le corpus en mots. Puisque nous répliquons un *tokenizer WordPiece* (comme BERT), nous utiliserons le *tokenizer* `bert-base-cased` pour la prétokénisation :

```python
from transformers import AutoTokenizer

tokenizer = AutoTokenizer.from_pretrained("bert-base-cased")
```

Ensuite, nous calculons les fréquences de chaque mot dans le corpus comme nous le faisons pour la prétokénisation :

```python
from collections import defaultdict

word_freqs = defaultdict(int)
for text in corpus:
    words_with_offsets = tokenizer.backend_tokenizer.pre_tokenizer.pre_tokenize_str(text)
    new_words = [word for word, offset in words_with_offsets]
    for word in new_words:
        word_freqs[word] += 1

word_freqs
```

```python out
defaultdict(
    int, {'This': 3, 'is': 2, 'the': 1, 'Hugging': 1, 'Face': 1, 'Course': 1, '.': 4, 'chapter': 1, 'about': 1,
    'tokenization': 1, 'section': 1, 'shows': 1, 'several': 1, 'tokenizer': 1, 'algorithms': 1, 'Hopefully': 1,
    ',': 1, 'you': 1, 'will': 1, 'be': 1, 'able': 1, 'to': 1, 'understand': 1, 'how': 1, 'they': 1, 'are': 1,
    'trained': 1, 'and': 1, 'generate': 1, 'tokens': 1})
```

Comme nous l'avons vu précédemment, l'alphabet est l'unique ensemble composé de toutes les premières lettres des mots, et de toutes les autres lettres qui apparaissent dans les mots préfixés par `##` :

```python
alphabet = []
for word in word_freqs.keys():
    if word[0] not in alphabet:
        alphabet.append(word[0])
    for letter in word[1:]:
        if f"##{letter}" not in alphabet:
            alphabet.append(f"##{letter}")

alphabet.sort()
alphabet

print(alphabet)
```

```python out
['##a', '##b', '##c', '##d', '##e', '##f', '##g', '##h', '##i', '##k', '##l', '##m', '##n', '##o', '##p', '##r', '##s',
 '##t', '##u', '##v', '##w', '##y', '##z', ',', '.', 'C', 'F', 'H', 'T', 'a', 'b', 'c', 'g', 'h', 'i', 's', 't', 'u',
 'w', 'y']
```

Nous ajoutons également les *tokens* spéciaux utilisés par le modèle au début de ce vocabulaire. Dans le cas de BERT, il s'agit de la liste `["[PAD]", "[UNK]", "[CLS]", "[SEP]", "[MASK]"]` :

```python
vocab = ["[PAD]", "[UNK]", "[CLS]", "[SEP]", "[MASK]"] + alphabet.copy()
```

Ensuite, nous devons diviser chaque mot, avec toutes les lettres qui ne sont pas les premières préfixées par `##` :

```python
splits = {
    word: [c if i == 0 else f"##{c}" for i, c in enumerate(word)]
    for word in word_freqs.keys()
}
```

Maintenant que nous sommes prêts pour l'entraînement, écrivons une fonction qui calcule le score de chaque paire. Nous devrons l'utiliser à chaque étape de l'entraînement :

```python
def compute_pair_scores(splits):
    letter_freqs = defaultdict(int)
    pair_freqs = defaultdict(int)
    for word, freq in word_freqs.items():
        split = splits[word]
        if len(split) == 1:
            letter_freqs[split[0]] += freq
            continue
        for i in range(len(split) - 1):
            pair = (split[i], split[i + 1])
            letter_freqs[split[i]] += freq
            pair_freqs[pair] += freq
        letter_freqs[split[-1]] += freq

    scores = {
        pair: freq / (letter_freqs[pair[0]] * letter_freqs[pair[1]])
        for pair, freq in pair_freqs.items()
    }
    return scores
```

Jetons un coup d'œil à une partie de ce dictionnaire après les premières divisions :

```python
pair_scores = compute_pair_scores(splits)
for i, key in enumerate(pair_scores.keys()):
    print(f"{key}: {pair_scores[key]}")
    if i >= 5:
        break
```

```python out
('T', '##h'): 0.125
('##h', '##i'): 0.03409090909090909
('##i', '##s'): 0.02727272727272727
('i', '##s'): 0.1
('t', '##h'): 0.03571428571428571
('##h', '##e'): 0.011904761904761904
```

Maintenant, trouver la paire avec le meilleur score ne prend qu'une rapide boucle :

```python
best_pair = ""
max_score = None
for pair, score in pair_scores.items():
    if max_score is None or max_score < score:
        best_pair = pair
        max_score = score

print(best_pair, max_score)
```

```python out
('a', '##b') 0.2
```

Ainsi, la première fusion à apprendre est `('a', '##b') -> 'ab'` et nous ajoutons `'ab'` au vocabulaire :

```python
vocab.append("ab")
```

Pour continuer, nous devons appliquer cette fusion dans notre dictionnaire `splits`. Écrivons une autre fonction pour cela :

```python
def merge_pair(a, b, splits):
    for word in word_freqs:
        split = splits[word]
        if len(split) == 1:
            continue
        i = 0
        while i < len(split) - 1:
            if split[i] == a and split[i + 1] == b:
                merge = a + b[2:] if b.startswith("##") else a + b
                split = split[:i] + [merge] + split[i + 2 :]
            else:
                i += 1
        splits[word] = split
    return splits
```

Et nous pouvons regarder le résultat de la première fusion :

```py
splits = merge_pair("a", "##b", splits)
splits["about"]
```

```python out
['ab', '##o', '##u', '##t']
```

Nous avons maintenant tout ce dont nous avons besoin pour boucler jusqu'à ce que nous ayons appris toutes les fusions que nous voulons. Visons une taille de vocabulaire de 70 :

```python
vocab_size = 70
while len(vocab) < vocab_size:
    scores = compute_pair_scores(splits)
    best_pair, max_score = "", None
    for pair, score in scores.items():
        if max_score is None or max_score < score:
            best_pair = pair
            max_score = score
    splits = merge_pair(*best_pair, splits)
    new_token = (
        best_pair[0] + best_pair[1][2:]
        if best_pair[1].startswith("##")
        else best_pair[0] + best_pair[1]
    )
    vocab.append(new_token)
```

Nous pouvons ensuite examiner le vocabulaire généré :

```py
print(vocab)
```

```python out
['[PAD]', '[UNK]', '[CLS]', '[SEP]', '[MASK]', '##a', '##b', '##c', '##d', '##e', '##f', '##g', '##h', '##i', '##k',
 '##l', '##m', '##n', '##o', '##p', '##r', '##s', '##t', '##u', '##v', '##w', '##y', '##z', ',', '.', 'C', 'F', 'H',
 'T', 'a', 'b', 'c', 'g', 'h', 'i', 's', 't', 'u', 'w', 'y', '##fu', 'Fa', 'Fac', '##ct', '##ful', '##full', '##fully',
 'Th', 'ch', '##hm', 'cha', 'chap', 'chapt', '##thm', 'Hu', 'Hug', 'Hugg', 'sh', 'th', 'is', '##thms', '##za', '##zat',
 '##ut']
```

Comme nous pouvons le voir, comparé à BPE, ce *tokenizer* apprend les parties de mots comme des *tokens* un peu plus rapidement.

> [!TIP]
> 💡 Utiliser `train_new_from_iterator()` sur le même corpus ne donnera pas exactement le même vocabulaire. C'est parce que la bibliothèque 🤗 *Tokenizers* n'implémente pas *WordPiece* pour l'entraînement (puisque nous ne sommes pas complètement sûrs de son fonctionnement interne), mais utilise le BPE à la place.

Pour tokeniser un nouveau texte, on le prétokenise, on le divise, puis on applique l'algorithme de tokenisation sur chaque mot. En d'autres termes, nous recherchons le plus grand sous-mot commençant au début du premier mot et le divisons. Puis nous répétons le processus sur la deuxième partie et ainsi de suite pour le reste de ce mot et les mots suivants dans le texte :

```python
def encode_word(word):
    tokens = []
    while len(word) > 0:
        i = len(word)
        while i > 0 and word[:i] not in vocab:
            i -= 1
        if i == 0:
            return ["[UNK]"]
        tokens.append(word[:i])
        word = word[i:]
        if len(word) > 0:
            word = f"##{word}"
    return tokens
```

Testons-le sur un mot qui fait partie du vocabulaire, et un autre qui n'en fait pas partie :

```python
print(encode_word("Hugging"))
print(encode_word("HOgging"))
```

```python out
['Hugg', '##i', '##n', '##g']
['[UNK]']
```

Maintenant, écrivons une fonction qui permet de tokeniser un texte :

```python
def tokenize(text):
    pre_tokenize_result = tokenizer._tokenizer.pre_tokenizer.pre_tokenize_str(text)
    pre_tokenized_text = [word for word, offset in pre_tokenize_result]
    encoded_words = [encode_word(word) for word in pre_tokenized_text]
    return sum(encoded_words, [])
```

On peut l'essayer sur n'importe quel texte :

```python
tokenize("This is the Hugging Face Course!")  # C'est le cours d'Hugging Face
```

```python out
['Th', '##i', '##s', 'is', 'th', '##e', 'Hugg', '##i', '##n', '##g', 'Fac', '##e', 'c', '##o', '##u', '##r', '##s',
 '##e', '[UNK]']
```

C'est tout pour l'algorithme *WordPiece* ! Maintenant, jetons un coup d'oeil à *Unigram*.
